package ru.ifmo.ctddev.larionov.task2;

import java.util.*;

public class LinkedBag<T> extends AbstractCollection<T> {

	private ListItem first, last;
	private Map<T, Set<ListItem>> map;
	private int size;
	private int currentRevision;

	private class ListItem {
		public T value;
		public ListItem next, prev;

		public ListItem(T v) {
			value = v;
		}
	}

	public LinkedBag() {
		map = new HashMap<T, Set<ListItem>>();
		create();
		currentRevision = 0;
	}

	private void create() {
		first = new ListItem(null);
		last = new ListItem(null);
		first.next = last;
		last.prev = first;
		size = 0;
	}

	public Iterator<T> iterator() {
		return new LinkedBagIterator(false);
	}

	public Iterator<T> reverseIterator() {
		return new LinkedBagIterator(true);
	}

	public int size() {
		return size;
	}

	public boolean add(T o) {
		if (!map.containsKey(o)) {
			map.put(o, new HashSet<ListItem>());
		}

		ListItem tmp = new ListItem(o);
		last.prev.next = tmp;
		tmp.next = last;
		tmp.prev = last.prev;
		last.prev = tmp;
		map.get(o).add(tmp);
		++size;
		++currentRevision;
		return true;
	}

	public void clear() {
		map.clear();
		create();
		++currentRevision;
	}

	public boolean contains(Object o) {
		return map.containsKey(o);
	}

	public boolean remove(Object o) {
		if (!map.containsKey(o)) {
			return false;
		} else {
			new LinkedBagIterator(map.get(o).iterator().next()).remove();
			++currentRevision;
			return true;
		}
	}

	private class LinkedBagIterator implements Iterator<T> {

		private ListItem current;
		private int currentIteratorRevision;
		private boolean flag, reverse;

		public LinkedBagIterator(boolean l) {
			currentIteratorRevision = currentRevision;
			flag = false;
			reverse = l;
			if (!reverse) {
				current = first.next;
			} else {
				current = last.prev;
			}
		}

		private LinkedBagIterator(ListItem x) {
			current = x.next;
			currentIteratorRevision = currentRevision;
			reverse = false;
		}

		private boolean isIteratorValid() {
			return currentIteratorRevision == currentRevision;
		}

		public boolean hasNext() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}

			if (!reverse) {
				return current != last;
			} else {
				return current != first;
			}
		}

		public T next() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}
			if ((!reverse && current == last) || (reverse && current == first)) {
				throw new NoSuchElementException();
			}

			T tmp = current.value;
			flag = false;
			if (!reverse) {
				current = current.next;
			} else {
				current = current.prev;
			}
			return tmp;
		}

		public void remove() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}
			if (flag || (!reverse && current == first.next)
					|| (reverse && current == last.prev)) {
				throw new IllegalStateException();
			}

			ListItem tmp;
			T tmpValue;
			if (!reverse) {
				tmp = current.prev;
				tmpValue = tmp.value;
				tmp.prev.next = current;
				current.prev = tmp.prev;

			} else {
				tmp = current.next;
				tmpValue = tmp.value;
				tmp.next.prev = current;
				current.next = tmp.next;
			}
			map.get(tmpValue).remove(tmp);
			if (map.get(tmpValue).isEmpty()) {
				map.remove(tmpValue);
			}
			flag = true;
			--size;
		}
	}
}